import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-02-22
 * Time: 14:44
 */

//[  Map 和 Set 使用场景  ]
//[  去重  Set           ]
//[  统计 k-v 模型用 Map  ]

//[hashCode()和equals()的关系是这样的:            ]
//[如果两个对象相等(equal),它们的hashcode一定相同;   ]
//[如果两个对象有相同的hashcode,它们不一定相等(equal);]



public class Test {

    //1.有十个【十万个】数据，去重
    public static void main1(String[] args) {
        Set<Integer> set = new HashSet<>();
        int[] array = {1,2,3,4,5,5,6,7,6,8,9};
        for (int x:array) {
            set.add(x);
        }
        System.out.println(set);
    }

    //2.有十个【十万个】数据，找到第一个重复的数据、
    public static void main2(String[] args) {
        Set<Integer> set = new HashSet<>();
        int[] array = {1,2,3,4,5,5,6,6,7,7,8,9};
        for (int x: array) {
            if (!set.contains(x)) {
                set.add(x);
            } else {
                System.out.println(x);
                return;
            }
        }
    }

    //3.统计10万个数据当中，每个数据出现的次数？
    public static void main3(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] array = {1,2,3,3,4,5,5,6,6,7,7,7,7,8,8,8,9,10,100,100};
        for (int x:array) {
            //一行代码解决
            map.put(x, map.getOrDefault(x,0)+1);
//            if (!map.containsKey(x)) {
//                map.put(x,1);
//            } else {
//                Integer ret = map.get(x)+1;
//                map.put(x,ret);
//            }
        }
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            if (entry.getValue() > 1) {
                System.out.println("key "+entry.getKey()+" val: "+entry.getValue());
            }
        }
    }

    //4.只出现一次的数字（其它数字都出现两次）
    public Integer find(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int x: array) {
            if (!set.contains(x)) {
                set.add(x);
            } else {
                set.remove(x);
            }
        }
        for (int x:array) {
            if (set.contains(x)) {
                return x;
            }
        }
        return -1;
    }

    //5.复制带随机指针的链表
    static class Node{
        public int val;
        public Node next;
        public Node random;
    }
    public Node copyRandomList(Node head) {
        if (head==null) {
            return null;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //创建结点
        while (cur!=null) {
            Node newNode = new Node();
            newNode.val = cur.val;
            map.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while (cur!=null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    //6.宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for(int i = 0;i<jewels.length();i++) {
            if (!set.contains(jewels.charAt(i))) {
                set.add(jewels.charAt(i));
            }
        }
        int count = 0;
        for(int j = 0;j<stones.length();j++) {
            if (set.contains(stones.charAt(j))) {
                count++;
            }
        }
        return count;
    }

    //7.旧键盘打字
    public static void func(String str1,String str2) {
        //全部转大写
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        Set<Character> set1 = new HashSet();
        //遍历实际输出字符串
        for(int i = 0;i < str2.length(); i++) {
            set1.add(str2.charAt(i));
        }
        Set<Character> set2 = new HashSet();
        for(int j = 0; j<str1.length();j++) {
            if (!set1.contains(str1.charAt(j)) && !set2.contains(str1.charAt(j))) {
                System.out.print(str1.charAt(j));
                set2.add(str1.charAt(j));
            }
        }

    }

    //8.前K个高频单词
    public static List<String> topKFrequent(String[] words, int k) {
        //1.建立 world-频率 映射关系
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s:words) {
            hashMap.put(s,hashMap.getOrDefault(s,0)+1);
        }

        //找出前top k个高频词汇-创建小堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            //需要重写Map.Entry集合当中的比较方法
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //当频率相等的时候，比较字典顺序
                if (o1.getValue().equals(o2.getValue())) {
                    //由于最后有一个反转，所以为了满足频率相等按字典序排雷，这里需要将字典序大的放堆顶[细节问题]
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //遍历hashMap，将里面的数据放入小堆
        for (Map.Entry<String,Integer> entry:hashMap.entrySet()) {
            //小根堆未放满时
            if (minHeap.size()<k) {
                minHeap.offer(entry);
            } else {
                //小根堆放满了，下面需要根堆顶元素比较
                //如果比堆顶元素大，就交换
                if (entry.getValue().compareTo(minHeap.peek().getValue())>0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    //如果单词的出现频率相同
                    if (entry.getValue().compareTo(minHeap.peek().getValue())==0) {
                        //如果比当前小堆顶元素在字典顺序靠前
                        if (entry.getKey().compareTo(minHeap.peek().getKey())<0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        //将前k个元素key添加到list集合中
        List<String> list = new ArrayList<>();
        for (int i = 0; i<k;i++) {
            String key = minHeap.poll().getKey();
            list.add(key);
        }
        //反转集合
        Collections.reverse(list);
        return list;


    }
    public static void main(String[] args) {
        //String[] words = {"a","b","a","c","d","a","c","e","e","a","e"};
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = topKFrequent(words,3);
        System.out.println(ret);
    }

}
